import sys
import time
from math import *
from line_algo import *
from geometry import *
shapes=('square','triangle','triangle')
def reverse(string):
    t=''
    for c in reversed(string):
        t=t+c
    return t
def readinfile(filename):
    f=open(filename,'r')
    r=f.readlines()
    
    f.close()
    arr=[]
    max_length_row = 0
    for line in r:
        line=line.replace('\r','')
        if line[len(line)-1]=='\n':
            arr.append(line[0:len(line)-1])
        else:
            arr.append(line)
        if(len(arr[-1:][0]) > max_length_row): max_length_row = len(arr[-1:][0])
    for i in range(len(arr)):
        arr[i] = arr[i] + ' ' * (max_length_row - len(arr[i]))
    return arr

class shape:
    def init(self, p_shape):
        self.name = p_shape.name
        self.points = p_shape.points
        self.edges = p_shape.edges
        self.line_segments = p_shape.line_segments
        self.vertices = p_shape.vertices

    def __lt__(self, obj):
        return self.compare_size(obj) < 0

    def __le__(self, obj):
        return self.compare_size(obj) <= 0

    def __ge__(self, obj):
        return self.compare_size(obj) >= 0

    def __gt__(self, obj):
        return self.compare_size(obj) > 0

    def compare_size(self, other):
        (min_x1, min_y1), (max_x1, max_y1) = self.bounding_box()
        (min_x2, min_y2), (max_x2, max_y2) = other.bounding_box()
        cmp = (max_x1 - min_x1) * (max_y1 - min_y1) - (max_x2 - min_x2) * (max_y2 - min_y2)
        return cmp
            
    def __init__(self, file = '', _name = '', p_line_segments = [], ):
        self.name=_name
        self.raw_shape = None
        if file != '': self.raw_shape=readinfile(file)
        self.points = []
        self.line_segments = []
        self.vertices = []
        self.edges = []
        if file != '': self.points=self.create_points()
        else:
            for i in range(len(p_line_segments)):                
                for j in range(i + 1, len(p_line_segments)):
                    p1, p2 = p_line_segments[i]
                    p3, p4 = p_line_segments[j]

                    if points_equal(p1, p3):   p_line_segments[j] = p1, p_line_segments[j][1]
                    elif points_equal(p1, p4): p_line_segments[j] = p_line_segments[j][0], p1
                    elif points_equal(p2, p3): p_line_segments[j] = p2, p_line_segments[j][1]                    
                    elif points_equal(p2, p4): p_line_segments[j] = p_line_segments[j][0], p2

            for (p1, p2) in p_line_segments:
                if p1 not in self.points: self.points.append(p1)
                if p2 not in self.points: self.points.append(p2)
        self.line_segments = p_line_segments
        if p_line_segments == []: self.line_segments = self.create_line_segments()
        self.vertices=vertices(self.points, self.line_segments)
        self.edges = self.__edges__(self.points, self.line_segments)

    def __equalize_points__(self):
        for i in range(len(self.line_segments)):                
                for j in range(i + 1, len(self.line_segments)):
                    p1, p2 = self.line_segments[i]
                    p3, p4 = self.line_segments[j]

                    if points_equal(p1, p3):   self.line_segments[j] = p1, self.line_segments[j][1]
                    elif points_equal(p1, p4): self.line_segments[j] = self.line_segments[j][0], p1
                    elif points_equal(p2, p3): self.line_segments[j] = p2, self.line_segments[j][1]                    
                    elif points_equal(p2, p4): self.line_segments[j] = self.line_segments[j][0], p2

    def __str__(self):
        string=""
        return object.__str__(self)
    def bounding_box(self):
        min_x, min_y, max_x, max_y = 0, 0, 0, 0
        for (x, y) in self.points:
            if(x < min_x): min_x = x
            if(x > max_x): max_x = x

            if(y < min_y): min_y = y
            if(y > max_y): max_y = y
        return (min_x, min_y), (max_x, max_y)

    def create_points(self):
        points=[]
        for r in range(len(self.raw_shape)):
            for c in range(len(self.raw_shape[r])):
                if self.raw_shape[r][c]=='.':
                    points.append((r,c))
        return points

    def __edges__(self):
        for p1, p2 in self.line_segments:
            
    def create_line_segments(self):
        line_segments=[]
        if len(self.points) == 0:
            return line_segments, []
        current_point=self.points[0]
        ordered_points=[current_point]
        points_used=[]
        while len(points_used) < len(self.points):
            (r, c) = current_point
            line0 = ''
            line2 = ''
            line1 = self.raw_shape[r]
            if r > 0: line0 = self.raw_shape[r-1]
            if r < len(self.raw_shape)-1: line2 = self.raw_shape[r+1]
            char_left = ''
            char_right = ''
            char_above = ''
            char_below = ''
            if c > 0: char_left = line1[c-1]
            if len(line1) > c + 1: char_right = line1[c+1]
            if len(line0) > c: char_above = line0[c]
            if len(line2) > c: char_below = line2[c]
            for char, row, col in [(char_left, r, c - 1), (char_right, r, c + 1), (char_above, r - 1, c), (char_below, r + 1, c)]:
                if char == '<' or char == '>' or char == '^' or char == '|':
                    break
                continue
            while self.raw_shape[row][col] != '.':
                if char == '<':
                    col = col - 1
                elif char == '>':
                    col = col + 1
                elif char == '^':
                    row = row - 1
                elif char == '|':
                    row = row + 1
                if row >= len(self.raw_shape):
                    print row, col
                    raise ValueError
                if col >= len(self.raw_shape[row]): continue
                if self.raw_shape[row][col] == '<' or self.raw_shape[row][col] == '>' or self.raw_shape[row][col] == '^' or self.raw_shape[row][col] == '|':
                    char = self.raw_shape[row][col]
                point2 = row, col
            points_used.append(point2)
            line_segments.append((current_point,point2))
            ordered_points.append(point2)
            current_point=point2
        #the last point in the ordered points should be the same as the first point, so we can remove it since it's a duplication of the first point
        point = ordered_points.pop()
        try:
            assert(point == ordered_points[0])
        except AssertionError:
            print 'error point:%s, ordered_points[0]:%s'%(point, ordered_points[0])
        assert(len(ordered_points) == len(self.points))
        self.__equalize_points__()
        return line_segments

    def flip(self):
        ns = []
        for point in self.points:
            ns.append(flip_point(point))
        line_segs = []
        for seg in self.line_segments:
            n1, n2 = seg
            line_segs.append((flip_point(n1), flip_point(n2)))
        
        verts = []

        for point, segs in self.vertices:
            s = []
            fpoint = flip_point(point)
            for i in range(len(segs)):
                (n1, n2) = segs[i]
                fn1 = flip_point(n1)
                fn2 = flip_point(n2)
                s.append((fn1, fn2))
            verts.append((fpoint, s))
        self.points = ns
        self.line_segments = line_segs
        self.__equalize_points__()
        self.vertices = verts
        self.flipped = not self.flipped

    def translate(self, (r,c)):
        new_points = []
        new_segments = []
        new_vertices = []
        for i in range(len(self.points)):
            (x, y) = self.points[i]
            new_points.append((x + r, y + c))
            
        for i in range(len(self.line_segments)):
            (point1, point2) = self.line_segments[i]
            n1 = (point1[0] + r, point1[1] + c)
            n2 = (point2[0] + r, point2[1] + c)
            new_segments.append((n1, n2))
        
        for i in range(len(self.vertices)):
            point, segments = self.vertices[i]
            n = (point[0] + r, point[1] + c)
            segs = []
            for j in range(len(segments)):
                (point1, point2) = segments[j]
                n1 = (point1[0] + r, point1[1] + c)
                n2 = (point2[0] + r, point2[1] + c)
                segs.append((n1, n2))
            new_vertices.append((n, segs))
        self.points = new_points
        self.line_segments = new_segments
        self.__equalize_points__()
        self.vertices = new_vertices

    def fast_rotate(self, p_point_of_rotation, cos_theta, sin_theta):
        self.translate((-p_point_of_rotation[0], -p_point_of_rotation[1]))
        new_points = []
        new_segments = []
        new_vertices = []
        for i in range(len(self.points)):
            new_points.append(fast_rotate2d(self.points[i], cos_theta, sin_theta))
        for i in range(len(self.line_segments)):
            point1, point2 = self.line_segments[i]
            new_segments.append((fast_rotate2d(point1, cos_theta, sin_theta), fast_rotate2d(point2, cos_theta, sin_theta)))
            self.line_segments[i] = point1, point2
        for i in range(len(self.vertices)):
            point, segments = self.vertices[i]
            point = fast_rotate2d(point, cos_theta, sin_theta)
            for j in range(len(segments)):
                point1, point2 = segments[j]
                point1 = fast_rotate2d(point1, cos_theta, sin_theta)
                point2 = fast_rotate2d(point2, cos_theta, sin_theta)
                segments[j] = point1, point2
            self.vertices[i] = point, segments

        self.points = new_points
        self.line_segments = new_segments
        self.__equalize_points__()
        self.translate(p_point_of_rotation)
        
    def rotate(self,p_point_of_rotation, p_angle):
        self.translate((-p_point_of_rotation[0], -p_point_of_rotation[1]))
        new_points = []
        new_segments = []
        new_vertices = []
        for i in range(len(self.points)):
            new_points.append(rotate2d(self.points[i], p_angle))
        for i in range(len(self.line_segments)):
            point1, point2 = self.line_segments[i]
            new_segments.append((rotate2d(point1, p_angle), rotate2d(point2, p_angle)))
            self.line_segments[i] = point1, point2
        for i in range(len(self.vertices)):
            point, segments = self.vertices[i]
            point = rotate2d(point, p_angle)
            for j in range(len(segments)):
                point1, point2 = segments[j]
                point1 = rotate2d(point1, p_angle)
                point2 = rotate2d(point2, p_angle)
                segments[j] = point1, point2
            self.vertices[i] = point, segments
        self.points = new_points
        self.line_segments = new_segments
        self.translate(p_point_of_rotation)
        self.__equalize_points__()
    def scale(self, x_scale, y_scale):
        new_segs = []
        new_points = []
        new_vertices = []
        for n in self.points:
            new_points.append(scale_vector(n, x_scale, y_scale))
        for (n1, n2) in self.line_segments:
            new_segs.append((scale_vector(n1, x_scale, y_scale),scale_vector(n2, x_scale, y_scale)))
        for vertex in self.vertices:
            new_vertices.append(scale_vertex(vertex, x_scale, y_scale))
        self.line_segments = new_segs
        self.points = new_points
        self.vertices = new_vertices
        self.__equalize_points__()

    def subtract_shape(self,p_shape):
        new_shape = subtract_shape(p_shape, self)
        return new_shape

def fitshapes2(p_shapes, p_shape_to_fit):
   l = []
   for p in p_shapes:
       for i in range(len(p.vertices)):
           l.append((p, i))
   return __fitshapes2__(l, p_shape_to_fit)

def __fitshapes2__(l, p_shape_to_fit):
    if len(l) == 0: return True
    sort_vertex_list(l)
    for (p, v1) in l:
        if vertex2_shape_fit(l, (p, v1), p_shape_to_fit):       
            return True
        p.flip()
        if vertex2_shape_fit(l, (p, v1), p_shape_to_fit):
            return True
        p.flip()
    return False

def sort_vertex_list(l):
    return
    
def vertex2_shape_fit(l, (p, v1), p_shape_to_fit):
    for v2 in p_shape_to_fit.vertices:            
        point1 = p.vertices[v1][0]
        point2 = v2[0]
        p.translate((point2[0] - point1[0], point2[1] - point1[1]))        
        for match in match_vertex_pair(p.vertices[v1], v2, p, p_shape_to_fit):
            if match:
                shape_to_fit = p_shape_to_fit.subtract_shape(p)
                l2 = remove_shape(l, p)
                if __fitshapes2__(l2, shape_to_fit):
                    return True
                
    return False

def remove_shape(l, p):
    i = 0
    l2 = []
    l2 = [x for x in l if id(x[0]) != id(p)]
    return l2

def fitshapes(p_shapes, p_shape_to_fit):
    #sort the shapes largest to smallest, by their bounding box size, look at __cmp__ for shape class for details
    p_shapes.sort(reverse = True)
    return __fitshapes__(p_shapes, p_shape_to_fit)

def __fitshapes__(p_shapes, p_shape_to_fit):
    if(len(p_shapes) == 0): return True
    #only 1 shape 
    elif len(p_shapes) == 1:
        return fitshape(p_shapes[0], p_shape_to_fit).next() 
    else:    
        for i in range(len(p_shapes)):
            shape = p_shapes[i]        
            for b in fitshape(shape, p_shape_to_fit):
                if b == True:
                    shape_to_fit = p_shape_to_fit.subtract_shape(shape)
                    #create a new array of shapes that doesn't include p_shapes[i]
                    shapes = p_shapes[:i]+p_shapes[i + 1:]
                    if __fitshapes__(shapes, shape_to_fit):
                        return True            
    return False

#try and fit p_shape to p_shape_to_fit. If it is possible to fit p_shape into p_shape_to_fit than return True AND position p_shape so that it is a subset of p_shape_to_fit 
#otherwise return False and leave p_shape as is.
def fitshape(p_shape, p_shape_to_fit):    
    gen = fit_vertices(p_shape, p_shape_to_fit)
    for fitted in gen:        
        if fitted == True:
            yield True
    p_shape.flip()
    for i in range(len(p_shape.vertices)):
        for j in fit_vertices(p_shape, p_shape_to_fit):
            if j == True:
                yield True
    p_shape.flip()
    yield False
        
def fit_vertices(shape1, shape2):
    """vertex1 is one of the vertices of p_shape
    The goal is to orient shape1 such that vertex1 coincides with one of the points of shape2 and shape1 is also
    contained inside of shape2. And the additional contraint that one of shape1's line segments is parallel to at
    least one of shape2's line segments."""
    for i in range(len(shape1.vertices)):
        point1 = shape1.vertices[i][0]
        for j in range(len(shape2.vertices)):            
            point2 = shape2.vertices[j][0]
            #translate vertex1 ontop of vertex2
            shape1.translate((point2[0] - point1[0], point2[1] - point1[1]))
            #for each segment1 in vertex1 and for each segment2, make segment1 parallel to segment2. This way we 
            #try all orientations that can make shape1 contained inside of shape2.
            for matched in match_vertex_pair(shape1.vertices[i], shape2.vertices[j], shape1, shape2):
                if(matched == True):
                    yield True
            shape1.translate((-point2[0] + point1[0], -point2[1] + point1[1]))
    yield False

def match_vertex_pair(vertex1, vertex2, shape1, shape2):
    (point1,segments1) = vertex1 
    (point2,segments2) = vertex2
    assert(points_equal(point1, point2))
#    if logging.on('match_vertex_pair'):
#        logging.log("point1 = " + str(point1))
#        logging.log("point2 = " + str(point2))
    #for each segment1 in vertex1 and for each segment2, make segment1 parallel to segment2. This way we 
    #try all orientations that can make shape1 contained inside of p_shape_to_fit.
    for segment1 in segments1:
        for segment2 in segments2:

            #translate so point2 is the origin
            tsegment1 = translate(segment1, (-point2[0], -point2[1]))
            tsegment2 = translate(segment2, (-point2[0], -point2[1]))

#            if logging.on('match_vertex_pair'):
#                logging.log("tsegment1 = " + str(tsegment1))
#                logging.log("tsegment2 = " + str(tsegment2))

            vec1 = tsegment1[0]
            if(points_equal(tsegment1[0], [0, 0])): vec1 = tsegment1[1]

            vec2 = tsegment2[0]
            if(points_equal(tsegment2[0], [0, 0])): vec2 = tsegment2[1]

            #theta1 is the angle that segment1 makes with the positive x-axis
            #0 <= theta1 < 2pi
            #theta1 = angle(vec1)

#            if logging.on('match_vertex_pair'):
#                logging.log("theta1 = " + str(theta1))

            #theta2 is the angle that segment2 makes with the positive x-axis
            #0 <= theta2 < 2pi

            if(mag(vec2) <= EPSILON):
                print "Error vec2 == 0"
                raise ValueError, p_shape_to_fit

            #theta2 = angle(vec2)

#            if logging.on('match_vertex_pair'):
#                logging.log("theta2 = " + str(theta2))
            vec1 = normalize(vec1)
            vec2 = normalize(vec2)            
            cos_theta = dot(vec1, vec2)
            sin_theta = cross(vec1, vec2)
            #rotation_angle = theta2 - theta1

#            if logging.on('match_vertex_pair'):
#                logging.log("rotation_angle = " + str(rotation_angle))
            p1 = fast_rotate2d(vec1, cos_theta, sin_theta)

            p1 = (p1[0] + point2[0], p1[1] + point2[1])
#            if logging.on('match_vertex_pair'):
#                logging.log("p1 = " + str(p1))
#                logging.log("p1 not inside = " + str(not inside_shape(p1, shape2) and not on_boundary(p1, shape2)))

            if not inside_shape(p1, shape2) and not on_boundary(p1, shape2):
                continue
            points = shape1.points[:]
            line_segments = shape1.line_segments[:]
            verts = shape1.vertices[:]
            #rotate segment1 into segment2
            shape1.fast_rotate(point2, cos_theta, sin_theta)
#            if logging.on('match_vertex_pair'):
#                yield True
            if subset(shape1, shape2):
                yield True
            shape1.points = points
            shape1.line_segments = line_segments
            shape1.vertices = verts
        
    yield False

#test if shape1 is a subset of shape2
def subset(shape1, shape2):
    """returns true if shape1 is a subset of shape2, returns false otherwise"""
    for (x, y) in shape1.points:
        if not inside_shape((x, y),shape2) and not on_boundary((x, y),shape2): 
            if logging.on('subset') == True:
                print 't1'
                print 'point1:(%f, %f)'%(r, c)
            return False
    for (point1,point2) in shape1.line_segments:
        if not segment_contained_in((point1,point2), shape2): 
            if logging.on('subset') == True:
                print 't2'
                print '(point1, point2):(%f, %f), (%f, %f)'%(point1[0], point1[1], point2[0], point2[1])
            return False
    #for (i,j) in shape2.points:
    #    if not on_boundary((i,j),shape1) and inside_shape((i,j),shape1):    return False
    return True
        
def intersect(shape1,shape2):
    """returns true if shape1 and shape2 intersect, returns false otherwise"""
    if subset(shape1, shape2) or subset(shape2, shape1):

        return True
    for (point1,point2) in shape1.line_segments:
        for (point3,point4) in shape2.line_segments:
            firstCoord, secondCoord = lineIntersection(point1,point2,point3,point4)
            if secondCoord != None and secondCoord['intersection'] == True and ('overlapped intersection' not in secondCoord) and ('endpoint intersection' not in secondCoord):

                return True

    return False#Yes I know this needs massive work

def intersections(p_shape,p_shapes):
    for shape in p_shapes:
        if intersect(shape,p_shape):  return True
    return False

#Subtract p_shape1 from p_shape2
def subtract_shape(p_shape1, p_shape2):
    new_line_segments = []
    if not subset(p_shape1, p_shape2): return None
    for line_segment1 in p_shape1.line_segments:
        split_seg = split_segment(line_segment1, p_shape2)
        #the part of the line segment that is outside p_shape2
        outside_part = split_seg['outside']
        #None of the line segment should be outside of p_shape2 since p_shape1 is a subset of p_shape2
        assert(outside_part == [])
        #the boundary part of a line segment does not form part of the boundary for the new shape, so we can ignore this part of the line segment
        boundary_part = split_seg['boundary']
        #this is the part of the line segment that will be included in the boundary of the new shape
        inside_part = split_seg['inside']
        new_line_segments.extend(inside_part)
    for line_segment2 in p_shape2.line_segments:
        split_seg = split_segment(line_segment2, p_shape1)
        #the part of the line segment that is outside p_shape1
        outside_part = split_seg['outside']
        if logging.on('subtract_shape'):
            print 'p_shape1:' 
            print str(p_shape1)
            print 'p_shape1.line_segments:'
            print p_shape1.line_segments
            print 'line_segment2:'
            print line_segment2
        new_line_segments.extend(outside_part)
        #the boundary part of a line segment does not form part of the boundary for the new shape, so we can ignore this part of the line segment
        boundary_part = split_seg['boundary']
        #this is the part of the line segment that will be included in the boundary of the new shape
        inside_part = split_seg['inside']
        #none of the line segments in p_shape2 should be in p_shape1 since p_shape1 is a subset of p_shape2
        if inside_part != []:
            print 'inside_part:'
            print inside_part
            print 'line_segment2:'
            print line_segment2
            raise ValueError, (p_shape1, p_shape2)
    
    #remove zero length line segments
    #zero length line segments are a result of floating point errors.
    for seg in new_line_segments:
        if(points_equal(seg[0], seg[1])):
               new_line_segments.remove(seg)
    return shape('', '', new_line_segments)
